package other;

/**题目：求回文子串的最大长度
 * 给定一个字符串，要求返回这个字符串能构建的最长的回文字符串
 * y : aaabccdd
 *      最长为：acdbdca
 * @Author Gavin
 * @date 2022.01.09 10:20
 */
public class solution_6 {
    /**
     * 解题思路：
     * 可以根据回文字符串的特点推算两个规律：
     * 1.如果给定字符串中每个字符的个数都是偶数，那么最长回文串长度就是这个字符长度
     * 2.统计字符串中字符为奇数的字符个数，为奇数的个数只能有一个位于回文串中心，其它的都要舍弃
     * 所以最长就为字符长度-字符奇数个数+1
     */
    public int solution(String s){
        //定义一个数组来保存字符串出现的次数
        int[] d=new int[256];
        int oddNum=0;
        for (char c:s.toCharArray()){
            ++d[c];
        }
        for (int count:d){
            if(count%2==1){
                oddNum++;
            }
        }
        int unUsed=Math.max(0,oddNum-1);
        return s.length()-unUsed;
    }
}
